// https://leetcode.cn/problems/max-points-on-a-line/?envType=study-plan-v2&envId=top-interview-150

// 算法思路总结：
// 1. 遍历每个点作为基准点，统计与其他点的斜率
// 2. 使用最简分数形式表示斜率，避免浮点数精度问题
// 3. 特殊处理水平和垂直线，统一符号表示
// 4. 记录重复点数量，合并统计最大共线点数
// 5. 时间复杂度：O(N²logN)，空间复杂度：O(N)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <map>

class Solution 
{
private:
    int gcd(int a, int b)
    {
        a = abs(a), b = abs(b);
        while (b > 0)
        {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
public:
    int maxPoints(vector<vector<int>>& points) 
    {
        int m = points.size();
        if (m <= 2) return m;

        int ret = 0;
        for (int i = 0 ; i < m ; i++)
        {
            if (m - i <= ret) break;

            const int x = points[i][0];
            const int y = points[i][1];

            map<pair<int, int>, int> count;
            int duplicate = 1;

            for (int j = i + 1 ; j < m ; j++)
            {
                int dx = points[j][0] - x;
                int dy = points[j][1] - y;

                if (dx == 0 && dy == 0)
                {
                    duplicate++;
                    continue;
                }
                else if (dx == 0)
                {
                    count[{0, 1}]++;
                }
                else if (dy == 0)
                {
                    count[{1, 0}]++;
                }
                else 
                {
                    int g = gcd(dx, dy);
                    dx /= g;
                    dy /= g;
                    if (dx < 0)
                    {
                        dx = -dx;
                        dy = -dy;
                    }
                    count[{dx, dy}]++;
                }
            }

            int maxNums = 0;
            for (const auto& [_, cnt] : count)
            {
                if (cnt > maxNums)
                {
                    maxNums = cnt;
                }
            }
            if (maxNums + duplicate > ret)
            {
                ret = maxNums + duplicate;
            }
        }

        return ret;
    }
};

int main()
{
    vector<vector<int>> points1 = {{1,1},{2,2},{3,3}};
    vector<vector<int>> points2 = {{1,1},{3,2},{5,3},{4,1},{2,3},{1,4}};

    Solution sol;

    cout << sol.maxPoints(points1) << endl;
    cout << sol.maxPoints(points2) << endl;

    return 0;
}